В этой статье мы рассмотрим самый быстрый алгоритм для ECDLP из области вычислительной теории чисел, кенгуру Полларда также называют алгоритм лямбды Полларда.

Метод кенгуру Полларда вычисляет дискретные логарифмы в произвольных циклических группах. Он применяется, если известно, что дискретный логарифм лежит в определенном диапазоне, скажем [ a , b ], а затем имеет ожидаемое время выполнения групповой операции.

Преимущество Pollard’s Kangaroo:

• использует очень мало памяти

• можно распараллелить с линейным ускорением

• можно эффективно отслеживать требования к объему памяти

Все это делает метод кенгуру самым мощным методом решения задачи дискретного логарифмирования.

Один из способов сломать схемы подписи ECDSA — это решить проблему дискретного логарифмирования.

В настройках ECDSA алгоритмы субэкспоненциального времени, такие как метод индексного исчисления, не применяются, а лучшим известным на сегодняшний день методом решения лежащем в их основе DLP являются метод кенгуру